package com.c2b.algorithm.leetcode.base;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 *
 * <a href='https://leetcode.cn/problems/delete-nodes-and-return-forest/'>删点成林(Delete Nodes And Return Forest)</a>
 * <p>给出二叉树的根节点 root，树上每个节点都有一个不同的值。</p>
 * <p>如果节点值在 to_delete 中出现，我们就把该节点从树上删去，最后得到一个森林（一些不相交的树构成的集合）。</p>
 * <p>返回森林中的每棵树。你可以按任意顺序组织答案。</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：root = [1,2,3,4,5,6,7], to_delete = [3,5]
 *      输出：[[1,2,null,4],[6],[7]]
 *
 * 示例 2：
 *      输入：root = [1,2,4,null,3], to_delete = [3]
 *      输出：[[1,2,4]]
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 *  <ul>
 *      <li>树中的节点数最大为 1000。</li>
 *      <li>每个节点都有一个介于 1 到 1000 之间的值，且各不相同。</li>
 *      <li>to_delete.length <= 1000</li>
 *      <li>to_delete 包含一些从 1 到 1000、各不相同的值。</li>
 *  </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/11/22 16:59
 */
public class LC1110DeleteNodesAndReturnForest_M {
    static class Solution {
        public List<TreeNode> delNodes(TreeNode root, int[] to_delete) {
            Set<Integer> toDeleted = new HashSet<>();
            for (int i : to_delete) {
                toDeleted.add(i);
            }
            List<TreeNode> resList = new ArrayList<>();
            if (delNodes(root, toDeleted, resList) != null) {
                resList.add(root);
            }
            return resList;
        }

        private TreeNode delNodes(TreeNode currNode, Set<Integer> to_delete, List<TreeNode> resList) {
            if (currNode == null) {
                return null;
            }
            currNode.left = delNodes(currNode.left, to_delete, resList);
            currNode.right = delNodes(currNode.right, to_delete, resList);
            // 是否包含
            boolean contains = to_delete.contains(currNode.val);
            if (contains) {
                if (currNode.left != null) {
                    resList.add(currNode.left);
                }
                if (currNode.right != null) {
                    resList.add(currNode.right);
                }
                return null;
            }
            return currNode;
        }
    }

    public static void main(String[] args) {
        TreeNode root1 = new TreeNode(1);
        root1.left = new TreeNode(2);
        root1.right = new TreeNode(3);
        root1.left.left = new TreeNode(4);
        root1.left.right = new TreeNode(5);
        root1.right.left = new TreeNode(6);
        root1.right.right = new TreeNode(7);

        TreeNode root2 = new TreeNode(1);
        root2.left = new TreeNode(2);
        root2.right = new TreeNode(3);
        root2.right.right = new TreeNode(4);


        Solution solution = new Solution();
        List<TreeNode> list1 = solution.delNodes(root1, new int[]{3, 5});
        List<TreeNode> list2 = solution.delNodes(root2, new int[]{2, 1});
        System.out.println();


    }
}
